On orthogonal ray graphs
From MaRDI portal
Publication:602682
DOI10.1016/j.dam.2010.06.002zbMath1222.05219MaRDI QIDQ602682
Shuichi Ueno, Anish Man Singh Shrestha, Satoshi Tayu
Publication date: 5 November 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.06.002
intersection graphs; (Two-directional) orthogonal ray graphs; bipartite posets of interval dimension two; circular arc graphs; edge-asteroids
05C75: Structural characterization of families of graphs
Related Items
Intersection Graphs of Rays and Grounded Segments, Bipartite Analogues of Comparability and Cocomparability Graphs, Recognition and drawing of stick graphs, Configurations of non-crossing rays and related problems, On the OBDD representation of some graph classes, Max point-tolerance graphs, Ferrers dimension of grid intersection graphs, Bandwidth of convex bipartite graphs and related graphs, Grid intersection graphs and order dimension, On forbidden induced subgraphs for unit disk graphs, A constant factor approximation algorithm for boxicity of circular arc graphs, On orthogonal ray trees, Colored ray configurations, Non-edge orientation and vertex ordering characterizations of some classes of bigraphs, Independent sets and hitting sets of bicolored rectangular families, Recognizing simple-triangle graphs by restricted 2-chain subgraph cover, A recognition algorithm for adjusted interval digraphs, On the complexity of recognizing Stick, BipHook and max point-tolerance graphs, On Evasion Games on Graphs, Jump Number of Two-Directional Orthogonal Ray Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Chordal bipartite graphs with high boxicity
- Domination in convex and chordal bipartite graphs
- Circular-arc graphs with clique cover number two
- Bipartite permutation graphs
- On grid intersection graphs
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- A special planar satisfiability problem and a consequence of its NP- completeness
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Coloring relatives of intervals on the plane. I: Chromatic number versus girth
- Linear-time recognition of circular-arc graphs
- On computing a longest path in a tree
- Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
- Permuting matrices to avoid forbidden submatrices
- List homomorphisms and circular arc graphs
- Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
- Doubly Lexical Orderings of Matrices
- Interval bigraphs and circular arc graphs
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- Efficient parallel algorithms for bipartite permutation graphs
