The geometric thickness of low degree graphs

Christian A. Duncan; David Eppstein; Stephen G. Kobourov

doi:10.1145/997817.997868

The geometric thickness of low degree graphs

Christian A. Duncan, David Eppstein, Stephen G. Kobourov

Computer Science

Research output: Contribution to conference › Paper › peer-review

48 Scopus citations

Abstract

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 × 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 × n grid. The results have implications in graph theory, graph drawing, and VLSI design.

Original language	English (US)
Pages	340-346
Number of pages	7
DOIs	https://doi.org/10.1145/997817.997868
State	Published - 2004
Event	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: Jun 9 2004 → Jun 11 2004

Other

Other	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Country/Territory	United States
City	Brooklyn, NY
Period	6/9/04 → 6/11/04

Keywords

Geometric thickness
Graph drawing
Graph thickness
Layered graphs
Rectangle visibility
Simultaneous embeddings

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/997817.997868

Cite this

@conference{73fedb21986d4b73a324f1f572f06176,

title = "The geometric thickness of low degree graphs",

abstract = "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 × 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 × n grid. The results have implications in graph theory, graph drawing, and VLSI design.",

keywords = "Geometric thickness, Graph drawing, Graph thickness, Layered graphs, Rectangle visibility, Simultaneous embeddings",

author = "Duncan, {Christian A.} and David Eppstein and Kobourov, {Stephen G.}",

year = "2004",

doi = "10.1145/997817.997868",

language = "English (US)",

pages = "340--346",

note = "Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) ; Conference date: 09-06-2004 Through 11-06-2004",

}

TY - CONF

T1 - The geometric thickness of low degree graphs

AU - Duncan, Christian A.

AU - Eppstein, David

AU - Kobourov, Stephen G.

PY - 2004

Y1 - 2004

N2 - 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 × 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 × n grid. The results have implications in graph theory, graph drawing, and VLSI design.

AB - 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 × 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 × n grid. The results have implications in graph theory, graph drawing, and VLSI design.

KW - Geometric thickness

KW - Graph drawing

KW - Graph thickness

KW - Layered graphs

KW - Rectangle visibility

KW - Simultaneous embeddings

UR - http://www.scopus.com/inward/record.url?scp=4544290539&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=4544290539&partnerID=8YFLogxK

U2 - 10.1145/997817.997868

DO - 10.1145/997817.997868

M3 - Paper

AN - SCOPUS:4544290539

SP - 340

EP - 346

T2 - Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)

Y2 - 9 June 2004 through 11 June 2004

ER -

The geometric thickness of low degree graphs

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this