Fast enumeration algorithms for non-crossing geometric graphs (2009)
Katoh, Naoki, Tanigawa, Shin-Ichi
A non-crossing geometric graph is a graph embedded on a set of points in the plane with non-crossing straight line segments. In this paper we present a general framework for enumerating non-crossing...
A Proof of the Molecular Conjecture (2009)
Katoh, Naoki, Tanigawa, Shin-ichi
A $d$-dimensional body-and-hinge framework is, roughly speaking, a structure consisting of rigid bodies connected by hinges in $d$-dimensional space. The generic infinitesimal rigidity of a...
Enumerating Constrained Non-crossing Minimally Rigid Frameworks (2008)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints, which we call constrained...
Enumeration of Optimal Pin-Jointed Bistable Compliant Mechanisms (2008)
Naoki Katoh, Makoto Ohsaki, Takuya Kinoshita, Shin-ichi Tanigawa, David Avis, Ileana Streinu
Recently, a new type of mechanism called compliant mechanism has been developed and applied mainly in the field of micro-mechanics. A compliant mechanism has flexible parts to stabilize the...
Enumerating constrained non-crossing minimally rigid frameworks (2008)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
Fast enumeration algorithms for non-crossing geometric graphs (2008)
Katoh, Naoki, Tanigawa, Shin-ichi
Proceedings of the twenty-fourth annual symposium on Computational geometry 2008, College Park, MD, USA, June 09-11, 2008
Geometric Spanner of Objects under L1 Distance (Computing and Combinatorics) (2008)
Zhu, Yongding, Xu, Jinhui, Yang, Yang, Katoh, Naoki, Tanigawa, Shin-ichi
Computing and combinatorics : 14th annual international conference, COCOON 2008, Dalian, China, June 27-29, 2008 : proceedings : (Lecture notes in computer science ; 5092)
Enumerating non-crossing minimally rigid frameworks (2007)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
Enumerating Constrained Non-crossing Geometric Spanning Trees (Computing and Combinatorics) (2007)
Katoh, Naoki, Tanigawa, Shin-ichi
Computing and combinatorics : 13th Annual International Conference, COCOON 2007 Banff, Canada, July 16-19, 2007 : proceedings : (Lecture notes in computer science ; 4598)
Enumerating Constrained Non-crossing Minimally Rigid Frameworks (2006)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints (also called constrained...
Enumerating planar minimally rigid graphs (2006)
David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-ichi Tanigawa
Motivated by the work of Kawamoto et al. [5], who first suggested the use of graph enumeration techniques as an engineering tool for finding an optimum mechanism design, we give an algorithm for...
Enumerating planar minimally rigid graphs (2006)
David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-ichi Tanigawa
Abstract. We present an algorithm for enumerating without repetitions all the planar (noncrossing) minimally rigid (Laman) graphs embedded on a given generic set of n points. Our algorithm is based...