@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",
}