Optimal polygonal representation of planar graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


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 languageEnglish (US)
Title of host publicationLATIN 2010
Subtitle of host publicationTheoretical Informatics - 9th Latin American Symposium, Proceedings
Number of pages16
StatePublished - 2010
Event9th Latin American Theoretical Informatics Symposium, LATIN 2010 - Oaxaca, Mexico
Duration: Apr 19 2010Apr 23 2010

Publication series

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


Other9th Latin American Theoretical Informatics Symposium, LATIN 2010

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Optimal polygonal representation of planar graphs'. Together they form a unique fingerprint.

Cite this