Name
Abstract | ||
|---|---|---|
A (weak) rectangle visibility representation, or simply an RVR, of a graph consists of an assignment of axis-aligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Given a graph with a fixed embedding in the plane, we show that the problem of testing whether this graph has an embedding-preserving RVR can be solved in polynomial time for general embedded graphs and in linear time for 1-plane graphs, i.e., for embedded graphs having at most one crossing per edge. The linear time algorithm uses three forbidden configurations, which extend the set known for straight-line drawings of 1-plane graphs. The algorithm first checks for the presence of these forbidden configurations in the input graph, and then either an embedding-preserving RVR is computed (also in linear time) or a forbidden configuration is reported as a negative witness. Finally, we discuss extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge. |
Year | DOI | Venue |
|---|---|---|
2018 | https://doi.org/10.1007/s00454-017-9939-y | Discrete & Computational Geometry |
Keywords | DocType | Volume |
Visibility representations,1-Planarity,Fixed embedding,Forbidden configuration,68U05,68R10,94C15 | Journal | 60 |
Issue | ISSN | Citations |
2 | 0179-5376 | 2 |
PageRank | References | Authors |
0.38 | 23 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Therese Biedl | 1 | 902 | 106.36 |
| Giuseppe Liotta | 2 | 1356 | 112.95 |
| Fabrizio Montecchiani | 3 | 261 | 37.42 |