On orthogonal ray trees

DOI10.1016/J.DAM.2015.07.034MaRDI QIDQ908312zbMATH OpenOpenAlexFDO

Authors Irina Mustaţă, Kousuke Nishikawa, Asahi Takaoka, Satoshi Tayu, Shuichi Ueno

Publication date 4 February 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.07.034

zbMATH Keywords

intersection graphsforbidden minorsedge-asteroidsorthogonal ray graphsorthogonal ray trees

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Network design and communication in computer systems (68M10)

Recommendations

• On orthogonal ray graphs
• On the recognition of four-directional orthogonal ray graphs
• Intersection graphs of orthodox paths in trees
• Constant threshold intersection graphs of orthodox paths in trees
• Intersection graphs of rays and grounded segments

Cites work

• scientific article; zbMATH DE number 4142090 (Why is no real title available?)
• A special planar satisfiability problem and a consequence of its NP- completeness
• Algorithmic graph theory and perfect graphs
• Bandwidth of convex bipartite graphs and related graphs
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Circular-arc graphs with clique cover number two
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• Efficient graph representations
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• Graph Classes: A Survey
• Graph theory
• Grid intersection graphs and boxicity
• Induced matchings in asteroidal triple-free graphs
• Intersection graphs of segments
• Jump number of two-directional orthogonal ray graphs
• List homomorphisms and circular arc graphs
• Maximum matching in a convex bipartite graph
• On computing a longest path in a tree
• On grid intersection graphs
• On orthogonal ray graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• The clique problem in ray intersection graphs
• Topics in Intersection Graph Theory
• Two remarks on circular arc graphs
• Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs

Cited in

(4)

• LATIN 2004: Theoretical Informatics
• On orthogonal ray graphs
• On the recognition of four-directional orthogonal ray graphs
• Intersection graphs of rays and grounded segments

This page was built for publication: On orthogonal ray trees

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