E" such that E
For Full-Text PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Finding a Maximal Outerplanar Spanning Subgraph of a Graph
Sumio MASUDA Toshinobu KASHIWABARA
IEICE TRANSACTIONS (1976-1990) Vol.E73 No.4 pp.532-538
Publication Date: 1990/04/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Algorithm, Data Structure and Computational Complexity
Full Text: PDF>>
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.