On orthogonal ray graphs
From MaRDI portal
Publication:602682
DOI10.1016/j.dam.2010.06.002zbMath1222.05219OpenAlexW1973275449MaRDI 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 graphsbipartite posets of interval dimension twocircular arc graphsedge-asteroids
Related Items
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 ⋮ A recognition algorithm for adjusted interval digraphs ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ Intersection Graphs of Rays and Grounded Segments ⋮ On Evasion Games on Graphs ⋮ Colored ray configurations ⋮ On the complexity of recognizing Stick, BipHook and max point-tolerance graphs ⋮ On orthogonal ray trees ⋮ Bandwidth of convex bipartite graphs and related graphs ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ Jump Number of Two-Directional Orthogonal Ray Graphs ⋮ Non-edge orientation and vertex ordering characterizations of some classes of bigraphs ⋮ Recognition and drawing of stick graphs ⋮ Grid intersection graphs and order dimension ⋮ On forbidden induced subgraphs for unit disk graphs ⋮ Independent sets and hitting sets of bicolored rectangular families ⋮ A constant factor approximation algorithm for boxicity of circular arc 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
