On the characterization of level planar trees by minimal patterns

Alejandro Estrella-Balderrama; J. Joseph Fowler; Stephen G. Kobourov

doi:10.1007/978-3-642-11805-0_9

On the characterization of level planar trees by minimal patterns

Alejandro Estrella-Balderrama, J. Joseph Fowler, Stephen G. Kobourov

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Scopus citations

Abstract

We consider characterizations of level planar trees. Healy et al. [8] characterized the set of trees that are level planar in terms of two minimal level non-planar (MLNP) patterns. Fowler and Kobourov [7] later proved that the set of patterns was incomplete and added two additional patterns. In this paper, we show that the characterization is still incomplete by providing new MLNP patterns not included in the previous characterizations. Moreover, we introduce an iterative method to create an arbitrary number of MLNP patterns, thus proving that the set of minimal patterns that characterizes level planar trees is infinite.

Original language	English (US)
Title of host publication	Graph Drawing - 17th International Symposium, GD 2009, Revised Papers
Pages	69-80
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-11805-0_9
State	Published - 2010
Event	17th International Symposium on Graph Drawing, GD 2009 - Chicago, IL, United States Duration: Sep 22 2009 → Sep 25 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5849 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	17th International Symposium on Graph Drawing, GD 2009
Country/Territory	United States
City	Chicago, IL
Period	9/22/09 → 9/25/09

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-11805-0_9

Cite this

Estrella-Balderrama, A., Fowler, J. J., & Kobourov, S. G. (2010). On the characterization of level planar trees by minimal patterns. In Graph Drawing - 17th International Symposium, GD 2009, Revised Papers (pp. 69-80). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5849 LNCS). https://doi.org/10.1007/978-3-642-11805-0_9

On the characterization of level planar trees by minimal patterns. / Estrella-Balderrama, Alejandro; Fowler, J. Joseph; Kobourov, Stephen G.
Graph Drawing - 17th International Symposium, GD 2009, Revised Papers. 2010. p. 69-80 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5849 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Estrella-Balderrama, A, Fowler, JJ & Kobourov, SG 2010, On the characterization of level planar trees by minimal patterns. in Graph Drawing - 17th International Symposium, GD 2009, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5849 LNCS, pp. 69-80, 17th International Symposium on Graph Drawing, GD 2009, Chicago, IL, United States, 9/22/09. https://doi.org/10.1007/978-3-642-11805-0_9

Estrella-Balderrama A, Fowler JJ, Kobourov SG. On the characterization of level planar trees by minimal patterns. In Graph Drawing - 17th International Symposium, GD 2009, Revised Papers. 2010. p. 69-80. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-11805-0_9

@inproceedings{93e1c6f321e64f2e99e5150674a73af3,

title = "On the characterization of level planar trees by minimal patterns",

abstract = "We consider characterizations of level planar trees. Healy et al. [8] characterized the set of trees that are level planar in terms of two minimal level non-planar (MLNP) patterns. Fowler and Kobourov [7] later proved that the set of patterns was incomplete and added two additional patterns. In this paper, we show that the characterization is still incomplete by providing new MLNP patterns not included in the previous characterizations. Moreover, we introduce an iterative method to create an arbitrary number of MLNP patterns, thus proving that the set of minimal patterns that characterizes level planar trees is infinite.",

author = "Alejandro Estrella-Balderrama and Fowler, {J. Joseph} and Kobourov, {Stephen G.}",

note = "Funding Information: This work was supported in part by NSF grant CCF-0545743.; 17th International Symposium on Graph Drawing, GD 2009 ; Conference date: 22-09-2009 Through 25-09-2009",

year = "2010",

doi = "10.1007/978-3-642-11805-0_9",

language = "English (US)",

isbn = "3642118046",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "69--80",

booktitle = "Graph Drawing - 17th International Symposium, GD 2009, Revised Papers",

}

TY - GEN

T1 - On the characterization of level planar trees by minimal patterns

AU - Estrella-Balderrama, Alejandro

AU - Fowler, J. Joseph

AU - Kobourov, Stephen G.

N1 - Funding Information: This work was supported in part by NSF grant CCF-0545743.

PY - 2010

Y1 - 2010

N2 - We consider characterizations of level planar trees. Healy et al. [8] characterized the set of trees that are level planar in terms of two minimal level non-planar (MLNP) patterns. Fowler and Kobourov [7] later proved that the set of patterns was incomplete and added two additional patterns. In this paper, we show that the characterization is still incomplete by providing new MLNP patterns not included in the previous characterizations. Moreover, we introduce an iterative method to create an arbitrary number of MLNP patterns, thus proving that the set of minimal patterns that characterizes level planar trees is infinite.

AB - We consider characterizations of level planar trees. Healy et al. [8] characterized the set of trees that are level planar in terms of two minimal level non-planar (MLNP) patterns. Fowler and Kobourov [7] later proved that the set of patterns was incomplete and added two additional patterns. In this paper, we show that the characterization is still incomplete by providing new MLNP patterns not included in the previous characterizations. Moreover, we introduce an iterative method to create an arbitrary number of MLNP patterns, thus proving that the set of minimal patterns that characterizes level planar trees is infinite.

UR - http://www.scopus.com/inward/record.url?scp=77951547402&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951547402&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-11805-0_9

DO - 10.1007/978-3-642-11805-0_9

M3 - Conference contribution

AN - SCOPUS:77951547402

SN - 3642118046

SN - 9783642118043

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 69

EP - 80

BT - Graph Drawing - 17th International Symposium, GD 2009, Revised Papers

T2 - 17th International Symposium on Graph Drawing, GD 2009

Y2 - 22 September 2009 through 25 September 2009

ER -

On the characterization of level planar trees by minimal patterns

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this