On orthogonal ray trees

DOI10.1016/J.DAM.2015.07.034zbMATH Open1329.05274OpenAlexW1153726246MaRDI QIDQ908312FDOQ908312

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

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

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)

Cites Work

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

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)