Name
Abstract | ||
|---|---|---|
We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, the so called $$B_0$$B0-VPG graphs. Recognizing this class is an NP-complete problem. Although, there exists a polynomial time algorithm for recognizing chordal $$B_0$$B0-VPG graphs. In this paper, we present a minimal forbidden induced subgraph characterization of $$B_0$$B0-VPG graphs restricted to block graphs. As a byproduct, the proof of the main theorem provides an alternative certifying recognition and representation algorithm for $$B_0$$B0-VPG graphs in the class of block graphs. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00373-017-1791-6 | Graphs and Combinatorics |
Keywords | Field | DocType |
Vertex intersection graphs,Paths on a grid,Forbidden induced subgraphs,Block graphs | Discrete mathematics,Indifference graph,Combinatorics,Clique-sum,Chordal graph,Cograph,Treewidth,Pathwidth,Mathematics,Trapezoid graph,Maximal independent set | Journal |
Volume | Issue | ISSN |
33 | 4 | 0911-0119 |
Citations | PageRank | References |
2 | 0.37 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Liliana Alcón | 1 | 59 | 14.43 |
| Flavia Bonomo | 2 | 226 | 28.95 |
| M. P. Mazzoleni | 3 | 12 | 4.05 |