TOPICS
Search

Good Drawing


A good drawing of a finite simple graph is a graph drawing in the plane in which every pair of distinct edges meets at most once, either at a common endpoint or at a proper graph crossing, and no three edges meet away from vertices (Schaefer 2018, p. 4). In particular, adjacent edges meet only at their common endpoint, and edges without a common endpoint cross at most once.

A good drawing is also called a simple drawing (Arroyo et al. 2023, p. 745). The convention excluding three edges from crossing at one point is sometimes omitted from the definition of a simple drawing (Arroyo et al. 2023, p. 746).

The graph crossing number of a finite simple graph can be attained by a good drawing. Self-crossings, crossings of adjacent edges, and repeated crossings of two edges can be removed by rerouting edges to reduce the number of graph crossings (Schaefer 2018, p. 5). However, a good drawing need not minimize that number. For example, the straight line drawing of the complete graph K_4 with its vertices at the corners of a square is good and has one graph crossing, although K_4 is a planar graph.


See also

Graph Crossing, Graph Crossing Number, Graph Drawing, Thrackle

Explore with Wolfram|Alpha

References

Arroyo, A.; Klute, F.; Parada, I.; Vogtenhuber, B.; Seidel, R.; and Wiedera, T. "Inserting One Edge into a Simple Drawing Is Hard." Disc. Comput. Geom. 69, 745-770, 2023. https://doi.org/10.1007/s00454-022-00394-9.Schaefer, M. Crossing Numbers of Graphs. Boca Raton, FL: CRC Press, 2018. https://doi.org/10.1201/9781315152394.

Cite this as:

Weisstein, Eric W. "Good Drawing." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GoodDrawing.html

Subject classifications