| Presentation | 2018-03-05 A recognition algorithm for simple-triangle graphs Asahi Takaoka, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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(n^2 overline{m})$ to $O(nm)$, where $n$, $m$, and $overline{m}$ are the number of vertices, edges, and non-edges of the graph, respectively. The algorithm uses the vertex ordering characterization in our previous paper 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 cocomparability graph has an orientation that is alternating and acyclic. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Alternately orientable graphs / Cocomparability graphs / Intersection graphs / PI graphs / Recognition algorithm / Simple-triangle graphs / Vertex ordering characterization |
| Paper # | COMP2017-50 |
| Date of Issue | 2018-02-26 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2018/3/5(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Osaka Prefecture Univ. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hiro Ito(Univ. of Electro-Comm.) |
| Vice Chair | Yushi Uno(Osaka Pref. Univ.) |
| Secretary | Yushi Uno(Seikei Univ.) |
| Assistant | |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A recognition algorithm for simple-triangle graphs |
| Sub Title (in English) | |
| Keyword(1) | Alternately orientable graphs |
| Keyword(2) | Cocomparability graphs |
| Keyword(3) | Intersection graphs |
| Keyword(4) | PI graphs |
| Keyword(5) | Recognition algorithm |
| Keyword(6) | Simple-triangle graphs |
| Keyword(7) | Vertex ordering characterization |
| 1st Author's Name | Asahi Takaoka |
| 1st Author's Affiliation | Kanagawa University(Kanagawa Univ.) |
| Date | 2018-03-05 |
| Paper # | COMP2017-50 |
| Volume (vol) | vol.117 |
| Number (no) | COMP-474 |
| Page | pp.pp.27-34(COMP), |
| #Pages | 8 |
| Date of Issue | 2018-02-26 (COMP) |