| Title:
|
A linear algorithm to recognize maximal generalized outerplanar graphs (English) |
| Author:
|
Cáceres, José |
| Author:
|
Márquez, Alberto |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
122 |
| Issue:
|
3 |
| Year:
|
1997 |
| Pages:
|
225-230 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
In this work, we get a combinatorial characterization for maximal generalized outerplanar graphs (mgo graphs). This result yields a recursive algorithm testing whether a graph is a mgo graph or not. (English) |
| Keyword:
|
outerplanar graph |
| Keyword:
|
generalized outerplanar graph |
| MSC:
|
05C10 |
| MSC:
|
05C75 |
| MSC:
|
05C85 |
| idZBL:
|
Zbl 0898.05017 |
| idMR:
|
MR1600871 |
| DOI:
|
10.21136/MB.1997.126148 |
| . |
| Date available:
|
2009-09-24T21:25:32Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/126148 |
| . |
| Reference:
|
[1] F. Hаrаry: Graph Theory.Addison Wesley, Reading Mass., 1969. MR 0256911 |
| Reference:
|
[2] J. E. Hopcroft аnd R. E. Tаrjаn: Dividing a graph into triconnected components.SIAM J. Comput. 2 (1973), 135-158. MR 0327391, 10.1137/0202012 |
| Reference:
|
[3] M. C. vаn Lier аnd R. H. J. M. Otten: C.A.D. of masks and wiring.T. H. Rept. 74-E-44, Dept. Elect. Engrg. Eindhoven University of Technology. |
| Reference:
|
[4] S. Mitchell: Linear algorithms to recognize outerplanar and maximal outerplanar graphs.Inform. Process. Lett. 9 (1979), 229-232. Zbl 0444.68055, MR 0552536, 10.1016/0020-0190(79)90075-9 |
| Reference:
|
[5] T. Nishizeki N. Chibа: Planar Graphs: Theory and Algoгithms.North-Holland, Amsterdam, 1969. |
| Reference:
|
[6] J. Sedláček: On a generalization of outerplanar graphs.Časopis Pěst. Mat. 113 (1988) 213-218. MR 0949046 |
| Reference:
|
[7] W. T. Tutte: A theory of 3-connected graphs.Indag. Math. 23 (1961), 441-455. Zbl 0101.40903, MR 0140094 |
| . |
