Graph ear decompositions and graph embeddings
- Additional Document Info
- View All
Ear decomposition of a graph has been extensively studied in relation to graph connectivity. In this paper, a connection of ear decomposition to graph embeddings is exhibited. It is shown that constructing a maximum-paired ear decomposition of a graph and constructing a maximum-genus embedding of the graph are polynomial-time equivalent. Applications of this connection is discussed.
SIAM JOURNAL ON DISCRETE MATHEMATICS
author list (cited authors)
Chen, J., & Kanchi, S. P.
complete list of authors