TOPICS
Search

Face-Width


The face-width, also called representativity, of a graph embedding in a closed surface other than the sphere is the smallest possible number of intersection points between the embedded graph and a closed curve in the surface that cannot be continuously contracted to a point (Mohar 1997). Face-width therefore measures how densely a particular embedding meets the noncontractible curves in the surface, and can vary between embeddings of the same graph.

Fiedler et al. (1995) showed that a nonplanar graph with a projective plane graph embedding of face-width r has graph genus |_r/2_|, where |_x_| is the floor function. Such a graph is therefore a toroidal graph iff r=2 or r=3. For sufficiently large r, the toroidal crossing number of the graph also grows at least quadratically with r (Gitler et al. 2008).


See also

Graph Embedding, Graph Genus, Projective Planar Graph, Projective Plane Graph Embedding, Toroidal Crossing Number, Toroidal Graph

Explore with Wolfram|Alpha

References

Fiedler, J. R.; Huneke, J. P.; Richter, R. B.; and Robertson, N. "Computing the Orientable Genus of Projective Graphs." J. Graph Th. 20, 297-308, 1995. https://doi.org/10.1002/jgt.3190200305.Gitler, I.; Hlinený, P.; Leaños, J.; and Salazar, G. "The Crossing Number of a Projective Graph Is Quadratic in the Face-Width." Elec. J. Combin. 15, R46, 2008. https://doi.org/10.37236/770.Mohar, B. "Face-Width of Embedded Graphs." Math. Slovaca 47, 35-63, 1997. https://dml.cz/handle/10338.dmlcz/133334.

Cite this as:

Weisstein, Eric W. "Face-Width." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Face-Width.html

Subject classifications