Back to Search
Start Over
GRAPH EAR DECOMPOSITIONS AND GRAPH EMBEDDINGS.
- Source :
-
SIAM Journal on Discrete Mathematics . 1999, Vol. 12 Issue 2, p229-242. 14p. - Publication Year :
- 1999
-
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 are discussed. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 12
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 13220234
- Full Text :
- https://doi.org/10.1137/S0895480196304234