On the structure of locally outerplanar graphs

Hung Lung Wang; Chun Yu Tseng; Jou Ming Chang

doi:10.1587/transfun.E98.A.1212

On the structure of locally outerplanar graphs

Hung Lung Wang, Chun Yu Tseng, Jou Ming Chang

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	1212-1215
Number of pages	4
Journal	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Volume	E98A
Issue number	6
DOIs	https://doi.org/10.1587/transfun.E98.A.1212
Publication status	Published - 2015 Jun 1
Externally published	Yes

Keywords

Geometric Graphs
Locally outerplanar graphs
Self-intersecting paths

ASJC Scopus subject areas

Signal Processing
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering
Applied Mathematics

Access to Document

10.1587/transfun.E98.A.1212

Cite this

@article{367622c951a942aea00f927b70bb314b,

title = "On the structure of locally outerplanar graphs",

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 = "Geometric Graphs, Locally outerplanar graphs, Self-intersecting paths",

author = "Wang, {Hung Lung} and Tseng, {Chun Yu} and Chang, {Jou Ming}",

note = "Publisher Copyright: {\textcopyright} 2015 The Institute of Electronics, Information and Communication Engineers.",

year = "2015",

month = jun,

day = "1",

doi = "10.1587/transfun.E98.A.1212",

language = "English",

volume = "E98A",

pages = "1212--1215",

journal = "IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences",

issn = "0916-8508",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "6",

}

TY - JOUR

T1 - On the structure of locally outerplanar graphs

AU - Wang, Hung Lung

AU - Tseng, Chun Yu

AU - Chang, Jou Ming

PY - 2015/6/1

Y1 - 2015/6/1

N2 - 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.

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.

KW - Geometric Graphs

KW - Locally outerplanar graphs

KW - Self-intersecting paths

UR - http://www.scopus.com/inward/record.url?scp=84930447745&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84930447745&partnerID=8YFLogxK

U2 - 10.1587/transfun.E98.A.1212

DO - 10.1587/transfun.E98.A.1212

M3 - Article

AN - SCOPUS:84930447745

SN - 0916-8508

VL - E98A

SP - 1212

EP - 1215

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 6

ER -

On the structure of locally outerplanar graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this