How to Draw a Tait-Colorable Graph

Richter, David (2011) How to Draw a Tait-Colorable Graph. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 353-364 (Official URL:

Full text not available from this repository.


Presented here are necessary and sufficient conditions for a cubic graph equipped with a Tait-coloring to have a drawing in the real projective plane where every edge is represented by a line segment, all of the lines supporting the edges sharing a common color are concurrent, and all of the supporting lines are distinct.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_32
Classifications:P Styles > P.999 Others
ID Code:1220

Repository Staff Only: item control page


Agol, I., Hass, J., Thurston, W.: The computational complexity of knot genus and spanning area. Trans. Amer. Math. Soc. 358(9), 3821–3850 (2006), (electronic),

Biggs, N.: Algebraic graph theory. cambridge Tracts in Mathematics, vol. 67, Cambridge University Press, London (1974)

Björner, A., Vergnas, M.L., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids, 2nd edn. Cambridge University Press, Cambridge (2000)

Bonnington, C.P., Little, C.H.C.: The Foundations of Topological Graph Theory. Springer, New York (1995)

Eppstein, D.: The topology of bendless three-dimensional orthogonal graph drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 78–89. Springer, Heidelberg (2009)

Eppstein, D., Mumford, E.: Steinitz theorems for orthogonal polyhedra (December 2009) arXiv:0912.0537

Ferri, M., Gagliardi, C., Grasselli, L.: A graph-theoretical representation of pl-manifolds—a survey on crystallizations. Aequationes Math. 31(2-3), 121–141 (1986)

Ivanov, S.V.: The computational complexity of basic decision problems in 3-dimensional topology. Geom. Dedicata 131, 1–26 (2008),

Keszegh, B., Pach, J., Pálvölgyi, D., Tóth, G.: Drawing cubic graphs with at most five slopes. Comput. Geom. 40(2), 138–147 (2008),

Richter, D.A.: Ghost symmetry and an analogue of Steinitz’s theorem. Contrib. Alg. Geom. ( to appear, 2010)

Richter-Gebert, J.: Realization Spaces of Polytopes. Lecture Notes in Mathematics, vol. 1643. Springer, Heidelberg (1996)

Richter-Gebert, J., Kortenkamp, U.H.: The interactive geometry software Cinderella. Springer-Verlag, Heidelberg (1999); with 1 CD-ROM (Windows, MacOS, UNIX and JAVA-1.1 platform)

Tutte, W.T.: Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 21. Addison-Wesley Publishing Company, Menlo Park (1984)