Thickness-2 Graphs

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

If the edges of a graph can be partitioned into two planar graphs, it has thickness 2 (a biplanar graph). This Demonstration shows some thickness-2 embeddings of various quartic graphs. In the first step a Hamiltonian cycle is chosen. One of the graphs, the icosidodecahedral graph (26), is planar and actually has thickness 1.

[more]

Non-planar quartic graphs have geometric thickness 2 [1], and therefore have thickness 2.

[less]

Contributed by: Ed Pegg Jr (September 2015)
Open content licensed under CC BY-NC-SA


Snapshots


Details

References

[1] Christian A. Duncan, David Eppstein and Stephen G. Kobourov, "The Geometric Thickness of Low Degree Graphs", 24 Dec 2003. http://arxiv.org/abs/cs/0312056.

[2] D. Eppstein. "The Geometry Junkyard: Layered Graph Drawing." (Sep 18, 2015) www.ics.uci.edu/~eppstein/junkyard/thickness.

[3] Wikipedia. "Thickness (Graph Theory)." (Sep 18, 2015) en.wikipedia.org/wiki/Thickness_(graph_theory).



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send