Optimal polygonal representation of planar graphs

E. R. Gansner; Y. F. Hu; M. Kaufmann; S. G. Kobourov

doi:10.1007/978-3-642-12200-2_37

Optimal polygonal representation of planar graphs

E. R. Gansner, Y. F. Hu, M. Kaufmann, S. G. Kobourov

Computer Science

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

7 Scopus citations

Abstract

In this paper, we consider the problem of representing graphs by polygons whose sides touch. We show that at least six sides per polygon are necessary by constructing a class of planar graphs that cannot be represented by pentagons. We also show that the lower bound of six sides is matched by an upper bound of six sides with a linear time algorithm for representing any planar graph by touching hexagons. Moreover, our algorithm produces convex polygons with edges with slopes 0, 1, -1.

Original language	English (US)
Title of host publication	LATIN 2010
Subtitle of host publication	Theoretical Informatics - 9th Latin American Symposium, Proceedings
Pages	417-432
Number of pages	16
DOIs	https://doi.org/10.1007/978-3-642-12200-2_37
State	Published - 2010
Event	9th Latin American Theoretical Informatics Symposium, LATIN 2010 - Oaxaca, Mexico Duration: Apr 19 2010 → Apr 23 2010

Publication series

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

Other

Other	9th Latin American Theoretical Informatics Symposium, LATIN 2010
Country/Territory	Mexico
City	Oaxaca
Period	4/19/10 → 4/23/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-12200-2_37

Cite this

Gansner, E. R., Hu, Y. F., Kaufmann, M., & Kobourov, S. G. (2010). Optimal polygonal representation of planar graphs. In LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings (pp. 417-432). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6034 LNCS). https://doi.org/10.1007/978-3-642-12200-2_37

Optimal polygonal representation of planar graphs. / Gansner, E. R.; Hu, Y. F.; Kaufmann, M. et al.
LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings. 2010. p. 417-432 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6034 LNCS).

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

Gansner, ER, Hu, YF, Kaufmann, M & Kobourov, SG 2010, Optimal polygonal representation of planar graphs. in LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6034 LNCS, pp. 417-432, 9th Latin American Theoretical Informatics Symposium, LATIN 2010, Oaxaca, Mexico, 4/19/10. https://doi.org/10.1007/978-3-642-12200-2_37

@inproceedings{af39fc4a4d3640ba8d117c610ffc84a0,

title = "Optimal polygonal representation of planar graphs",

abstract = "In this paper, we consider the problem of representing graphs by polygons whose sides touch. We show that at least six sides per polygon are necessary by constructing a class of planar graphs that cannot be represented by pentagons. We also show that the lower bound of six sides is matched by an upper bound of six sides with a linear time algorithm for representing any planar graph by touching hexagons. Moreover, our algorithm produces convex polygons with edges with slopes 0, 1, -1.",

author = "Gansner, {E. R.} and Hu, {Y. F.} and M. Kaufmann and Kobourov, {S. G.}",

year = "2010",

doi = "10.1007/978-3-642-12200-2_37",

language = "English (US)",

isbn = "3642121993",

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

pages = "417--432",

booktitle = "LATIN 2010",

note = "9th Latin American Theoretical Informatics Symposium, LATIN 2010 ; Conference date: 19-04-2010 Through 23-04-2010",

}

TY - GEN

T1 - Optimal polygonal representation of planar graphs

AU - Gansner, E. R.

AU - Hu, Y. F.

AU - Kaufmann, M.

AU - Kobourov, S. G.

PY - 2010

Y1 - 2010

N2 - In this paper, we consider the problem of representing graphs by polygons whose sides touch. We show that at least six sides per polygon are necessary by constructing a class of planar graphs that cannot be represented by pentagons. We also show that the lower bound of six sides is matched by an upper bound of six sides with a linear time algorithm for representing any planar graph by touching hexagons. Moreover, our algorithm produces convex polygons with edges with slopes 0, 1, -1.

AB - In this paper, we consider the problem of representing graphs by polygons whose sides touch. We show that at least six sides per polygon are necessary by constructing a class of planar graphs that cannot be represented by pentagons. We also show that the lower bound of six sides is matched by an upper bound of six sides with a linear time algorithm for representing any planar graph by touching hexagons. Moreover, our algorithm produces convex polygons with edges with slopes 0, 1, -1.

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

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

U2 - 10.1007/978-3-642-12200-2_37

DO - 10.1007/978-3-642-12200-2_37

M3 - Conference contribution

AN - SCOPUS:77953511033

SN - 3642121993

SN - 9783642121999

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

SP - 417

EP - 432

BT - LATIN 2010

T2 - 9th Latin American Theoretical Informatics Symposium, LATIN 2010

Y2 - 19 April 2010 through 23 April 2010

ER -

Optimal polygonal representation of planar graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this