Geodesic
Recognizing Stick Graphs with and without Length Constraints
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019 , Tome 24 (2020) no. 4, pp. 657-681.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Stick graphs are intersection graphs of horizontal and vertical line segments that all touch a line of slope $-1$ and lie above this line. De Luca et al. [De Luca et al. GD'18] considered the recognition problem of stick graphs when no order is given ($\textsf{STICK}$), when the order of either one of the two sets is given ($\textsf{STICK}_{\textsf A}$), and when the order of both sets is given ($\textsf{STICK}_{\textsf{AB}}$). They showed how to solve $\textsf{STICK}_{\textsf{AB}}$ efficiently. In this paper, we improve the running time of their algorithm, and we solve $\textsf{STICK}_{\textsf A}$ efficiently. Further, we consider variants of these problems where the lengths of the sticks are given as input. We show that these variants of $\textsf{STICK}$, $\textsf{STICK}_{\textsf A}$, and $\textsf{STICK}_{\textsf{AB}}$ are all NP-complete. On the positive side, we give an efficient solution for $\textsf{STICK}_{\textsf{AB}}$ with fixed stick lengths if there are no isolated vertices.
DOI : 10.7155/jgaa.00524
Keywords: stick graphs, intersection graphs, grid intersection graphs, segment graphs, bipartite graphs, recognition problem, sweep-line, NP-hardness, linear program 
@article{JGAA_2020_24_4_a5,
     author = {Steven Chaplick and Philipp Kindermann and Andre L\"offler and Florian Thiele and Alexander Wolff and Alexander Zaft and Johannes Zink},
     title = {Recognizing {Stick} {Graphs} with and without {Length} {Constraints}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {657--681},
     publisher = {mathdoc},
     volume = {24},
     number = {4},
     year = {2020},
     doi = {10.7155/jgaa.00524},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00524/}
}
TY  - JOUR
AU  - Steven Chaplick
AU  - Philipp Kindermann
AU  - Andre Löffler
AU  - Florian Thiele
AU  - Alexander Wolff
AU  - Alexander Zaft
AU  - Johannes Zink
TI  - Recognizing Stick Graphs with and without Length Constraints
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 657
EP  - 681
VL  - 24
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00524/
DO  - 10.7155/jgaa.00524
LA  - en
ID  - JGAA_2020_24_4_a5
ER  - 
%0 Journal Article
%A Steven Chaplick
%A Philipp Kindermann
%A Andre Löffler
%A Florian Thiele
%A Alexander Wolff
%A Alexander Zaft
%A Johannes Zink
%T Recognizing Stick Graphs with and without Length Constraints
%J Journal of Graph Algorithms and Applications
%D 2020
%P 657-681
%V 24
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00524/
%R 10.7155/jgaa.00524
%G en
%F JGAA_2020_24_4_a5
Steven Chaplick; Philipp Kindermann; Andre Löffler; Florian Thiele; Alexander Wolff; Alexander Zaft; Johannes Zink. Recognizing Stick Graphs with and without Length Constraints. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-seventh International Symposium on Graph Drawing and Network Visualization, GD 2019
					, Tome 24 (2020) no. 4, pp. 657-681. doi : 10.7155/jgaa.00524. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00524/

Cité par Sources :