Vertex Contact Graphs of Paths on a Grid
作者： Nieke Aerts , Stefan Felsner
DOI: 10.1007/978-3-319-12340-0_5
关键词: Physics 、 Indifference graph 、 Chordal graph 、 Disjoint sets 、 Interior point method 、 Vertex separator 、 Combinatorics 、 Vertex (geometry) 、 Neighbourhood (graph theory) 、 Maximal independent set
摘要: We study Vertex Contact representations of Paths on a Grid (VCPG). In such representation the vertices \(G\) are represented by family interiorly disjoint grid-paths. Adjacencies contacts between an endpoint one grid-path and interior point another grid-path. Defining \(u \rightarrow v\) if path \(u\) ends \(v\) we obtain orientation from VCPG. To get hand bends grid is not enough. therefore consider pairs (\(\alpha ,\psi \)): 2-orientation \(\alpha \) flow \(\psi in angle graph. The describes behavior its two ends. give necessary sufficient condition for pair \((\alpha \)) to be realizable as
springer.com
core.ac.uk
sci-hub.st 参考文章(14)
Stefan Felsner, Rectangle and Square Representations of Planar Graphs Thirty Essays on Geometric Graph Theory. pp. 213- 248 ,(2013) , 10.1007/978-1-4614-0110-0_12
Thirty essays on geometric graph theory Springer. ,(2013) , 10.1007/978-1-4614-0110-0
Ulrich Fößmeier, Goos Kant, Michael Kaufmann, 2-Visibility Drawings of Planar Graphs graph drawing. pp. 155- 168 ,(1996) , 10.1007/3-540-62495-3_45
Stephen Kobourov, Torsten Ueckerdt, Kevin Verbeek, Combinatorial and geometric properties of planar laman graphs symposium on discrete algorithms. pp. 1668- 1678 ,(2013) , 10.5555/2627817.2627937
H. de Fraysseix, P. O. de Mendez, J. Pach, A left-first search algorithm for planar graphs Discrete & Computational Geometry. ,vol. 13, pp. 459- 468 ,(1995) , 10.1007/BF02574056
Roberto Tamassia, On embedding a graph in the grid with the minimum number of bends SIAM Journal on Computing. ,vol. 16, pp. 421- 444 ,(1987) , 10.1137/0216030
Steven Chaplick, Torsten Ueckerdt, Planar Graphs as VPG-Graphs Journal of Graph Algorithms and Applications. ,vol. 17, pp. 475- 494 ,(2013) , 10.7155/JGAA.00300
H. de Fraysseix, P. Ossona de Mendez, On topological aspects of orientations Discrete Mathematics. ,vol. 229, pp. 57- 72 ,(2001) , 10.1016/S0012-365X(00)00201-6
Martin Charles Golumbic, Gila Morgenstern, Edge Intersection Graphs of Paths on a Grid 50 Years of Combinatorics, Graph Theory, and Computing. ,vol. 16, pp. 193- 209 ,(2019) , 10.1201/9780429280092-11
Markus Schäffter, Drawing graphs on rectangular grids Discrete Applied Mathematics. ,vol. 63, pp. 75- 89 ,(1995) , 10.1016/0166-218X(94)00020-E