Recognizing Simple-Triangle Graphs by Restricted 2-Chain Subgraph Cover

详细信息    查看全文

• 关键词：Chain cover ; Graph sandwich problem ; PI graphs ; Simple ; triangle graphs ; Threshold dimension 2 graphs
• 刊名：Lecture Notes in Computer Science
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：10167
• 期：1
• 页码：177-189
• 丛书名：WALCOM: Algorithms and Computation
• ISBN：978-3-319-53925-6
• 卷排序：10167

文摘

A simple-triangle graph (also known as a PI graph) is the intersection graph of a family of triangles defined by a point on a horizontal line and an interval on another horizontal line. The recognition problem for simple-triangle graphs was a longstanding open problem, and recently a polynomial-time algorithm has been given (SIAM J. Discrete Math. 29(3):1150–1185, 2015). Along with the approach of this paper, we show a simpler recognition algorithm for simple-triangle graphs. To do this, we provide a polynomial-time algorithm to solve the following problem: Given a bipartite graph G and a set F of edges of G, find a 2-chain subgraph cover of G such that one of two chain subgraphs has no edges in F.