
doi: 10.7155/jgaa.00181
Summary: A straight-line grid drawing of a planar graph \(G\) is a drawing of \(G\) on an integer grid such that each vertex is drawn as a grid point and each edge is drawn as a straight-line segment without edge crossings. It is well known that a planar graph of \(n\) vertices admits a straight-line grid drawing on a grid of area \(O(n^2)\). A lower bound of \(\Omega(n^2)\) on the area-requirement for straight-line grid drawings of certain planar graphs are also known. In this paper, we introduce a fairly large class of planar graphs which admits a straight-line grid drawing on a grid of area \(O(n)\). We give a linear-time algorithm to find such a drawing. Our new class of planar graphs, which we call ``doughnut graphs'', is a subclass of 5-connected planar graphs. We show several interesting properties of ``doughnut graphs'' in this paper. One can easily observe that any spanning subgraph of a ``doughnut graph'' also admits a straight-line grid drawing with linear area. But the recognition of a spanning subgraph of a ``doughnut graph'' seems to be a non-trivial problem, since the recognition of a spanning subgraph of a given graph is an NP-complete problem in general. We establish a necessary and sufficient condition for a 4-connected planar graph \(G\) to be a spanning subgraph of a ``doughnut graph''. We also give a linear-time algorithm to augment a 4-connected planar graph \(G\) to a ``doughnut graph'' if \(G\) satisfies the necessary and sufficient condition.
linear-time algorithm, Graph theory (including graph drawing) in computer science, doughnut graph
linear-time algorithm, Graph theory (including graph drawing) in computer science, doughnut graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
