Finding a Maximal Outerplanar Spanning Subgraph of a Graph

Sumio MASUDA; Toshinobu KASHIWABARA

Finding a Maximal Outerplanar Spanning Subgraph of a Graph

Sumio MASUDA, Toshinobu KASHIWABARA

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on transactions Vol.E73-E No.4 pp.532-538

Publication Date: 1990/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithm, Data Structure and Computational Complexity

Authors

Sumio MASUDA
Toshinobu KASHIWABARA

Keyword

Cite this

Copy

Sumio MASUDA, Toshinobu KASHIWABARA, "Finding a Maximal Outerplanar Spanning Subgraph of a Graph" in IEICE TRANSACTIONS on transactions, vol. E73-E, no. 4, pp. 532-538, April 1990, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/transactions/10.1587/e73-e_4_532/_p

Copy

@ARTICLE{e73-e_4_532,
author={Sumio MASUDA, Toshinobu KASHIWABARA, },
journal={IEICE TRANSACTIONS on transactions},
title={Finding a Maximal Outerplanar Spanning Subgraph of a Graph},
year={1990},
volume={E73-E},
number={4},
pages={532-538},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Finding a Maximal Outerplanar Spanning Subgraph of a Graph
T2 - IEICE TRANSACTIONS on transactions
SP - 532
EP - 538
AU - Sumio MASUDA
AU - Toshinobu KASHIWABARA
PY - 1990
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E73-E
IS - 4
JA - IEICE TRANSACTIONS on transactions
Y1 - April 1990
AB - 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.
ER -