On orthogonal ray graphs

DOI10.1016/J.DAM.2010.06.002MaRDI QIDQ602682zbMATH OpenOpenAlexFDO

Authors Anish Man Singh Shrestha, Satoshi Tayu, Shuichi Ueno

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

zbMATH Keywords

intersection graphs(Two-directional) orthogonal ray graphsbipartite posets of interval dimension twocircular arc graphsedge-asteroids

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Recommendations

• On orthogonal ray trees
• On the recognition of four-directional orthogonal ray graphs
• Intersection graphs of rays and grounded segments
• Intersection graphs of rays and grounded segments
• On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs

Cites work

• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 739017 (Why is no real title available?)
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Bipartite permutation graphs
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Chordal bipartite graphs with high boxicity
• Circular-arc graphs with clique cover number two
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• Domination in convex and chordal bipartite graphs
• Doubly Lexical Orderings of Matrices
• Efficient parallel algorithms for bipartite permutation graphs
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Interval bigraphs and circular arc graphs
• Linear-time recognition of circular-arc graphs
• List homomorphisms and circular arc graphs
• On computing a longest path in a tree
• On grid intersection graphs
• Permuting matrices to avoid forbidden submatrices
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs

Cited in

(23)

• Ferrers dimension of grid intersection graphs
• Max point-tolerance graphs
• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• Bandwidth of convex bipartite graphs and related graphs
• Configurations of non-crossing rays and related problems
• A constant factor approximation algorithm for boxicity of circular arc graphs
• Bi-arc digraphs: recognition algorithm and applications
• On orthogonal ray trees
• A recognition algorithm for adjusted interval digraphs
• Min orderings and list homomorphism dichotomies for graphs and signed graphs
• Independent sets and hitting sets of bicolored rectangular families
• Intersection graphs of rays and grounded segments
• On the recognition of four-directional orthogonal ray graphs
• Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs
• Grid intersection graphs and order dimension
• Colored ray configurations
• On forbidden induced subgraphs for unit disk graphs
• On the OBDD representation of some graph classes
• Jump number of two-directional orthogonal ray graphs
• On evasion games on graphs
• Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
• On the complexity of recognizing Stick, BipHook and max point-tolerance graphs
• Bipartite Analogues of Comparability and Cocomparability Graphs

This page was built for publication: On orthogonal ray graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q602682)