Name
Abstract | ||
|---|---|---|
A graph G is a B0-VPG graph if one can associate a horizontal or vertical path on a rectangular grid with each vertex such that two vertices are adjacent if and only if the corresponding paths intersect in at least one grid-point. A graph G is a contact B0-VPG graph if it is a B0-VPG graph admitting a representation with no one-point paths, no two paths crossing, and no two paths sharing an edge of the grid. In this paper, we present a minimal forbidden induced subgraph characterisation of contact B0-VPG graphs within four special graph classes: chordal graphs, tree-cographs, P4-tidy graphs and P5-free graphs. Moreover, we present a polynomial-time algorithm for recognising chordal contact B0-VPG graphs. (c) 2019 Elsevier B.V. All rights reserved. <comment>Superscript/Subscript Available</comment |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.dam.2019.10.008 | DISCRETE APPLIED MATHEMATICS |
Keywords | DocType | Volume |
Chordal graph, Tree-cograph, P < sub > 4 <, sub >-tidy graph, P < sub > 5 <, sub >-free graph, Contact B < sub > 0 <, sub >-VPG graph | Journal | 308 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Flavia Bonomo | 1 | 226 | 28.95 |
| M. P. Mazzoleni | 2 | 12 | 4.05 |
| Mariano Leonardo Rean | 3 | 0 | 0.34 |
| Bernard Ries | 4 | 176 | 28.68 |