Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs

被引：7

作者：

Alcon, Liliana ^{[1
]}

Bonomo, Flavia ^{[2
,3
]}

Mazzoleni, Maria Pia ^{[1
,4
]}

机构：

[1] FCE UNLP, Dept Matemat, La Plata, Buenos Aires, Argentina

[2] Univ Buenos Aires, Fac Ciencias Exactas & Nat, Dept Computac, Buenos Aires, DF, Argentina

[3] Univ Buenos Aires, CONICET, Inst Invest Ciencias Computac ICC, Buenos Aires, DF, Argentina

[4] Consejo Nacl Invest Cient & Tecn, La Plata, Buenos Aires, Argentina

来源：

GRAPHS AND COMBINATORICS | 2017年 / 33卷 / 04期

关键词：

Vertex intersection graphs; Paths on a grid; Forbidden induced subgraphs; Block graphs; SEGMENTS;

D O I：

10.1007/s00373-017-1791-6

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, the so called -VPG graphs. Recognizing this class is an NP-complete problem. Although, there exists a polynomial time algorithm for recognizing chordal -VPG graphs. In this paper, we present a minimal forbidden induced subgraph characterization of -VPG graphs restricted to block graphs. As a byproduct, the proof of the main theorem provides an alternative certifying recognition and representation algorithm for -VPG graphs in the class of block graphs.

引用

页码：653 / 664

页数：12

共 9 条

[1]

[Anonymous], 2007, GRAPH THEORY

[2] Vertex intersection graphs of paths on a grid [J].

Asinowski, Andrei ;

Cohen, Elad ;

Golumbic, Martin Charles ;

Limouzy, Vincent ;

Lipshteyn, Marina ;

Stern, Michal .

Journal of Graph Algorithms and Applications, 2012, 16 (02) :129-150

[3] STRETCHING A KNOCK-KNEE LAYOUT FOR MULTILAYER WIRING [J].

BRADY, ML ;

SARRAFZADEH, M .

IEEE TRANSACTIONS ON COMPUTERS, 1990, 39 (01) :148-151

[4]

Chaplick S, 2011, LECT NOTES COMPUT SC, V6986, P319, DOI 10.1007/978-3-642-25870-1_29

[5] On the Intersection Graphs of Orthogonal Line Segments in the Plane: Characterizations of Some Subclasses of Chordal Graphs [J].

Golumbic, M. C. ;

Ries, B. .

GRAPHS AND COMBINATORICS, 2013, 29 (03) :499-517

[6]

Harary F., 1966, Publ. Math. (Debr.), V13, P19

[7] INTERSECTION GRAPHS OF SEGMENTS [J].

KRATOCHVIL, J ;

MATOUSEK, J .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1994, 62 (02) :289-315

[8]

Molitor P., 1991, EIK J INFORMATION PR, V27, P3

[9] TOPOLOGY OF THIN FILM RC CIRCUITS [J].

SINDEN, FW .

BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09) :1639-+

← 1 →