11 citations · 16 across the 9 of their papers we have counts for
10 papers
Finding Order-Preserving Subgraphs
Haruya Imamura, Yasuaki Kobayashi, Yota Otachi +5
(Induced) Subgraph Isomorphism and Maximum Common (Induced) Subgraph are fundamental problems in graph pattern matching and similarity computation. In graphs derived from time-seri…
Forbidden patterns of graphs 12-representable by pattern-avoiding words
Asahi Takaoka
A graph is -representable if there is a word over such that two vertices and with are adjacent if and o…
Computing shortest 12-representants of labeled graphs
Asahi Takaoka
The notion of -representable graphs was introduced as a variant of a well-known class of word-representable graphs. Recently, these graphs were shown to be equivalent to the co…
Graph classes equivalent to 12-representable graphs
Asahi Takaoka
Jones et al. (2015) introduced the notion of -representable graphs, where is a word over different from , as a generalization of word-representable gra…
Linear-semiorders and their incomparability graphs
Asahi Takaoka
A linear-interval order is the intersection of a linear order and an interval order. For this class of orders, several structural results have been known. This paper introduces a n…
A recognition algorithm for adjusted interval digraphs
Asahi Takaoka
Min orderings give a vertex ordering characterization, common to some graphs and digraphs such as interval graphs, complements of threshold tolerance graphs (known as co-TT graphs)…
A recognition algorithm for simple-triangle graphs
Asahi Takaoka
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 t…
A vertex ordering characterization of simple-triangle graphs
Asahi Takaoka
Consider two horizontal lines in the plane. A pair of a point on the top line and an interval on the bottom line defines a triangle between two lines. The intersection graph of suc…
Recognizing Simple-Triangle Graphs by Restricted 2-Chain Subgraph Cover
Asahi Takaoka
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…
Graph isomorphism completeness for trapezoid graphs
Asahi Takaoka
The complexity of the graph isomorphism problem for trapezoid graphs has been open over a decade. This paper shows that the problem is GI-complete. More precisely, we show that the…