The Geometric Thickness of Low Degree Graphs
| dc.creator | Duncan, Christian A. | |
| dc.creator | Eppstein, David | |
| dc.creator | Kobourov, Stephen G. | |
| dc.date | 2003-12-24 | |
| dc.date.accessioned | 2026-07-07T03:20:47Z | |
| dc.date.available | 2026-07-07T03:20:47Z | |
| dc.description | We prove that the geometric thickness of graphs whose maximum degree is no more than four is two. All of our algorithms run in O(n) time, where n is the number of vertices in the graph. In our proofs, we present an embedding algorithm for graphs with maximum degree three that uses an n x n grid and a more complex algorithm for embedding a graph with maximum degree four. We also show a variation using orthogonal edges for maximum degree four graphs that also uses an n x n grid. The results have implications in graph theory, graph drawing, and VLSI design. | |
| dc.description | 10 pages, 7 figures, submitted to SoCG 2004 | |
| dc.identifier | https://arxiv.org/abs/cs/0312056 | |
| dc.identifier | http://arxiv.org/abs/cs/0312056 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31951 | |
| dc.subject | Computational Geometry | |
| dc.subject | Discrete Mathematics | |
| dc.subject | I.3.5; F.2.2; G.2.2 | |
| dc.title | The Geometric Thickness of Low Degree Graphs | |
| dc.type | text |