2017/10/18 by Asahi Takaoka, Takaoka, Asahi
Computer Science · Mathematics · #05C62 #05C75 #05C85 #68R10 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #cs.DS #math.CO #msc:05C62 #msc:05C75 #msc:05C85 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1710.06559
revised, results unchanged, reference changed. 12 pages 12pt, 1 figure
arxiv created 2018/09/19 · arxiv updated 2018/09/20
A simple-triangle graph is the intersection graph of triangles that are defined by a point on a horizontal line and an interval on another horizontal line. The time complexity of the recognition problem for simple-triangle graphs was a longstanding open problem, which was recently settled. This paper provides a new recognition algorithm for simple-triangle graphs to improve the time bound from O(n2 m) to O(nm), where n, m, and m are the number of vertices, edges, and non-edges of the graph, respectively. The algorithm uses the vertex ordering characterization that a graph is a simple-triangle graph if and only if there is a linear ordering of the vertices containing both an alternating orientation of the graph and a transitive orientation of the complement of the graph. We also show, as a byproduct, that an alternating orientation can be obtained in O(nm) time for cocomparability graphs, and it is NP-complete to decide whether a graph has an orientation that is alternating and acyclic.