 Home
 Search Results
 Page 1 of 1
Search for: All records

Total Resources3
 Resource Type

30
 Availability

30
 Author / Contributor
 Filter by Author / Creator


De Luca, Felice (3)

Kobourov, Stephen (2)

Ahmed, Reyan (1)

Devkota, Sabin (1)

Di Giacomo, Emilio (1)

Didimo, Walter (1)

Hossain, Iqbal (1)

Kobourov, Stephen G (1)

Li, Mingwei (1)

Liotta, Giuseppe (1)

Lubiw, Anna (1)

Mondal, Debajyoti (1)

#Tyler Phillips, Kenneth E. (0)

& AbreuRamos, E. D. (0)

& Ahmed, Khadija. (0)

& AkcilOkan, O. (0)

& Akuom, D. (0)

& Aleven, V. (0)

& AndrewsLarson, C. (0)

& Archibald, J. (0)

 Filter by Editor


& Spizer, S. M. (0)

& . Spizer, S. (0)

& Ahn, J. (0)

& Bateiha, S. (0)

& Bosch, N. (0)

& Chen, B. (0)

& Chen, Bodong (0)

& Drown, S. (0)

& Higgins, A. (0)

& Kali, Y. (0)

& RuizArias, P.M. (0)

& S. Spitzer (0)

& Spitzer, S. (0)

& Spitzer, S.M. (0)

:Chaosong Huang, Gang Lu (0)

A. Agarwal (0)

A. Beygelzimer (0)

A. E. Lischka (0)

A. E. Lischka, E. B. (0)

A. E. Lischka, E.B. Dyer (0)


Have feedback or suggestions for a way to improve these results?
!
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

De Luca, Felice ; Di Giacomo, Emilio ; Didimo, Walter ; Kobourov, Stephen ; Liotta, Giuseppe ( , Journal of Graph Algorithms and Applications)

De Luca, Felice ; Hossain, Iqbal ; Kobourov, Stephen ; Lubiw, Anna ; Mondal, Debajyoti ( , 26th Symposium on Graph Drawing (GD))A Stick graph is an intersection graph of axisaligned segments such that the left endpoints of the horizontal segments and the bottom endpoints of the vertical segments lie on a “ground line,” a line with slope −1. It is an open question to decide in polynomial time whether a given bipartite graph G with bipartition A∪B has a Stick representation where the vertices in A and B correspond to horizontal and vertical segments, respectively. We prove that G has a Stick representation if and only if there are orderings of A and B such that G’s bipartite adjacency matrix with rows A and columns B excludes three small ‘forbidden’ submatrices. This is similar to characterizations for other classes of bipartite intersection graphs. We present an algorithm to test whether given orderings of A and B permit a Stick representation respecting those orderings, and to find such a representation if it exists. The algorithm runs in time linear in the size of the adjacency matrix. For the case when only the ordering of A is given, we present an O(AB}^3)time algorithm.