Optimal Polygonal Representation of Planar Graphs

Details Optimal Polygonal Representation of Planar Graphs Optimal Polygonal Representation of Planar Graphs

2011-04-08

arxiv.org/abs/1104.1482v1

Computer Science

Computational Geometry

26 pages, 14 figures. A preliminary version appeared in LATIN 2010, Oaxaca, Mexico

Scientific paper

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 having at most three slopes and with all vertices lying on an O(n)xO(n) grid.

Affiliated with

Also associated with

No associations

Rating

Optimal Polygonal Representation of Planar Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Polygonal Representation of Planar Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Polygonal Representation of Planar Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-353978