The Geometric Thickness of Low Degree Graphs

Details The Geometric Thickness of Low Degree Graphs The Geometric Thickness of Low Degree Graphs

2003-12-24

arxiv.org/abs/cs/0312056v1

Computer Science

Computational Geometry

10 pages, 7 figures, submitted to SoCG 2004

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Geometric Thickness of Low Degree 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 The Geometric Thickness of Low Degree Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Geometric Thickness of Low Degree Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-640752