For k ≥ 3, a convex geometric graph is called k-locally outerplanar if no path of length k intersects itself. In [D. Boutin, Convex Geometric Graphs with No Short Self-intersecting Path, Congressus Numerantium 160 (2003) 205-214], Boutin stated the results of the degeneracy for 3-locally outerplanar graphs. Later, in [D. Boutin, Structure and Properties of Locally Outerplanar Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 60 (2007) 169-180], a structural property on k-locally outerplanar graphs was proposed. These results are based on the existence of “minimal corner pairs”. In this paper, we show that a “minimal corner pair” may not exist and give a counterexample to disprove the structural property. Furthermore, we generalize the result on the degeneracy with respect to k-locally outerplanar graphs.
Hung-Lung WANG
National Taipei University of Business
Chun-Yu TSENG
National Taipei University of Business
Jou-Ming CHANG
National Taipei University of Business
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Hung-Lung WANG, Chun-Yu TSENG, Jou-Ming CHANG, "On the Structure of Locally Outerplanar Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E98-A, no. 6, pp. 1212-1215, June 2015, doi: 10.1587/transfun.E98.A.1212.
Abstract: For k ≥ 3, a convex geometric graph is called k-locally outerplanar if no path of length k intersects itself. In [D. Boutin, Convex Geometric Graphs with No Short Self-intersecting Path, Congressus Numerantium 160 (2003) 205-214], Boutin stated the results of the degeneracy for 3-locally outerplanar graphs. Later, in [D. Boutin, Structure and Properties of Locally Outerplanar Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 60 (2007) 169-180], a structural property on k-locally outerplanar graphs was proposed. These results are based on the existence of “minimal corner pairs”. In this paper, we show that a “minimal corner pair” may not exist and give a counterexample to disprove the structural property. Furthermore, we generalize the result on the degeneracy with respect to k-locally outerplanar graphs.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.1212/_p
Copy
@ARTICLE{e98-a_6_1212,
author={Hung-Lung WANG, Chun-Yu TSENG, Jou-Ming CHANG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Structure of Locally Outerplanar Graphs},
year={2015},
volume={E98-A},
number={6},
pages={1212-1215},
abstract={For k ≥ 3, a convex geometric graph is called k-locally outerplanar if no path of length k intersects itself. In [D. Boutin, Convex Geometric Graphs with No Short Self-intersecting Path, Congressus Numerantium 160 (2003) 205-214], Boutin stated the results of the degeneracy for 3-locally outerplanar graphs. Later, in [D. Boutin, Structure and Properties of Locally Outerplanar Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 60 (2007) 169-180], a structural property on k-locally outerplanar graphs was proposed. These results are based on the existence of “minimal corner pairs”. In this paper, we show that a “minimal corner pair” may not exist and give a counterexample to disprove the structural property. Furthermore, we generalize the result on the degeneracy with respect to k-locally outerplanar graphs.},
keywords={},
doi={10.1587/transfun.E98.A.1212},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - On the Structure of Locally Outerplanar Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1212
EP - 1215
AU - Hung-Lung WANG
AU - Chun-Yu TSENG
AU - Jou-Ming CHANG
PY - 2015
DO - 10.1587/transfun.E98.A.1212
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2015
AB - For k ≥ 3, a convex geometric graph is called k-locally outerplanar if no path of length k intersects itself. In [D. Boutin, Convex Geometric Graphs with No Short Self-intersecting Path, Congressus Numerantium 160 (2003) 205-214], Boutin stated the results of the degeneracy for 3-locally outerplanar graphs. Later, in [D. Boutin, Structure and Properties of Locally Outerplanar Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing 60 (2007) 169-180], a structural property on k-locally outerplanar graphs was proposed. These results are based on the existence of “minimal corner pairs”. In this paper, we show that a “minimal corner pair” may not exist and give a counterexample to disprove the structural property. Furthermore, we generalize the result on the degeneracy with respect to k-locally outerplanar graphs.
ER -