The Geometric Thickness of Low-Degree Graphs

Title: The Geometric Thickness of Low-Degree Graphs

Research Question: Can the geometric thickness of a graph be bounded as a function of its degree?

Methodology: The researchers used graph theory, planar embeddings, and algorithms to investigate the geometric thickness of graphs with a maximum degree of three and four.

Results: The authors proved that the geometric thickness of graphs with a maximum degree of three is two. They also presented efficient algorithms for embedding these graphs on a grid, using straight-line segments for the edges. For graphs with a maximum degree of four, they provided a more complex algorithm. They showed that the geometric thickness of these graphs is also two, using an n × n grid.

Implications: These results have implications for graph theory, graph drawing, and VLSI design. They provide bounds on the geometric thickness of low-degree graphs, which can be useful in various applications, such as visualizing software development and designing circuits. The algorithms presented in the paper are efficient and easy to implement, making them practical for use in these applications.

Link to Article: https://arxiv.org/abs/0312056v1 Authors: arXiv ID: 0312056v1