E" such that E E"E. In this paper, we present a linear-time algorithm for finding an mosg of a given graph." />


Finding a Maximal Outerplanar Spanning Subgraph of a Graph

Sumio MASUDA  Toshinobu KASHIWABARA  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E73   No.4   pp.532-538
Publication Date: 1990/04/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Algorithm, Data Structure and Computational Complexity
Keyword: 


Full Text: PDF>>
Buy this Article




Summary: 
A graph is said to be outerplanar if it has a planar embedding in which all vertices lie on the exterior face. For a graph G=(V, E), its spanning subgraph G =(V, E ) is called a maximal outerplanar spanning subgraph (abbreviated as mosg) if G is outerplanar and (V, E") is not outerplanar for any edge set E" such that E E"E. In this paper, we present a linear-time algorithm for finding an mosg of a given graph.