Graph ear decompositions and graph embeddings Academic Article

abstract

• 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.

authors

• Chen, Jianer

published proceedings

• SIAM JOURNAL ON DISCRETE MATHEMATICS

author list (cited authors)

• Chen, J., & Kanchi, S. P.

citation count

• 3

complete list of authors

• Chen, J||Kanchi, SP

publication date

• January 1999

publisher

• Society for Industrial & Applied Mathematics (SIAM)  Publisher

published in

• SIAM Journal on Discrete Mathematics  Journal

keywords

• Algorithm
• Ear Decomposition
• Graph Connectivity
• Graph Embedding
• Graph Maximum Genus

Digital Object Identifier (DOI)

• 10.1137/S0895480196304234

start page

• 229

end page

• 242

volume

• 12

issue

• 2

URL

• http%3A%2F%2Fdx.doi.org%2F10.1137%2Fs0895480196304234