Xin He

According to our database, Xin He authored at least 78 papers between 1987 and 2022.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2022

On Petrie cycle and Petrie tour partitions of 3- and 4-regular plane graphs.

Xin He, Huaming Zhang, Yijie Han

Math. Struct. Comput. Sci., 2022

More Efficient Parallel Integer Sorting.

Yijie Han, Xin He

Int. J. Found. Comput. Sci., 2022

2020

On Characterization of Petrie Partitionable Plane Graphs.

Xin He, Huaming Zhang

Proceedings of the Theory and Applications of Models of Computation, 2020

2016

Nearest Neighbor Interchange and Related Distances.

Bhaskar DasGupta, Xin He, Ming Li, John Tromp, Louxin Zhang

Encyclopedia of Algorithms, 2016

Nearly optimal monotone drawing of trees.

Dayu He, Xin He

Theor. Comput. Sci., 2016

2015

A Linear Time Algorithm for Determining Almost Bipartite Graphs.

Dayu He, Xin He

Proceedings of the Theory and Applications of Models of Computation, 2015

Star Shaped Orthogonal Drawing.

Xin He, Dayu He

Proceedings of the Theory and Applications of Models of Computation, 2015

Monotone Drawings of 3-Connected Plane Graphs.

Xin He, Dayu He

Proceedings of the Algorithms - ESA 2015, 2015

Compact Monotone Drawing of Trees.

Xin He, Dayu He

Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014

Succinct strictly convex greedy drawing of 3-connected plane graphs.

Jiun-Jie Wang, Xin He

Theor. Comput. Sci., 2014

On Succinct Greedy Drawings of Plane Triangulations and 3-Connected Plane Graphs.

Xin He, Huaming Zhang

Algorithmica, 2014

2013

A simple routing algorithm based on Schnyder coordinates.

Xin He, Huaming Zhang

Theor. Comput. Sci., 2013

2012

Compact visibility representation of 4-connected plane graphs.

Xin He, Jiun-Jie Wang, Huaming Zhang

Theor. Comput. Sci., 2012

Visibility Representation of Plane Graphs with Simultaneous Bound for Both Width and Height.

Jiun-Jie Wang, Xin He

J. Graph Algorithms Appl., 2012

2011

On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs.

Xin He, Huaming Zhang

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

A generalized greedy routing algorithm for 2-connected graphs.

Huaming Zhang, Xin He

Theor. Comput. Sci., 2010

Schnyder Greedy Routing Algorithm.

Xin He, Huaming Zhang

Proceedings of the Theory and Applications of Models of Computation, 7th Annual Conference, 2010

2009

Optimal <i>st</i> -orientations for plane triangulations.

Huaming Zhang, Xin He

J. Comb. Optim., 2009

2008

Nearest Neighbor Interchange and Related Distances.

Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Louxin Zhang

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Nearly Optimal Visibility Representations of Plane Graphs.

Xin He, Huaming Zhang

SIAM J. Discret. Math., 2008

2006

Communication-optimal parallel parenthesis matching.

Chun-Hsi Huang, Xin He, Min Qian

Parallel Comput., 2006

On simultaneous straight-line grid embedding of a planar graph and its dual.

Huaming Zhang, Xin He

Inf. Process. Lett., 2006

An Application of Well-orderly Trees in Graph Drawing.

Huaming Zhang, Xin He

Int. J. Found. Comput. Sci., 2006

Finding Hamiltonian paths in tournaments on clusters.

Chun-Hsi Huang, Sanguthevar Rajasekaran, Laurence Tianruo Yang, Xin He

Clust. Comput., 2006

2005

On Even Triangulations of 2-Connected Embedded Graphs.

Huaming Zhang, Xin He

SIAM J. Comput., 2005

Visibility representation of plane graphs via canonical ordering tree^,.

Huaming Zhang, Xin He

Inf. Process. Lett., 2005

Canonical Ordering Trees and Their Applications in Graph Drawing.

Huaming Zhang, Xin He

Discret. Comput. Geom., 2005

Improved visibility representation of plane graphs.

Huaming Zhang, Xin He

Comput. Geom., 2005

2004

Disk Embeddings of Planar Graphs.

Zhi-Zhong Chen, Xin He

Algorithmica, 2004

On Visibility Representation of Plane Graphs.

Huaming Zhang, Xin He

Proceedings of the STACS 2004, 2004

New Theoretical Bounds of Visibility Representation of Plane Graphs.

Huaming Zhang, Xin He

Proceedings of the Graph Drawing, 12th International Symposium, 2004

2003

Common-Face Embeddings of Planar Graphs.

Zhi-Zhong Chen, Xin He, Ming-Yang Kao

SIAM J. Comput., 2003

Compact Visibility Representation and Straight-Line Grid Embedding of Plane Graphs.

Huaming Zhang, Xin He

Proceedings of the Algorithms and Data Structures, 8th International Workshop, 2003

2002

Finding Double Euler Trails of Planar Graphs in Linear Time.

Zhi-Zhong Chen, Xin He, Chun-Hsi Huang

SIAM J. Comput., 2002

Average-Case Communication-Optimal Parallel Parenthesis Matching.

Chun-Hsi Huang, Xin He

Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

A Simple Linear Time Algorithm for Finding Even Triangulations of 2-Connected Bipartite Plane Graphs.

Huaming Zhang, Xin He

Proceedings of the Algorithms, 2002

2001

Communication Efficient BSP Algorithm for All Nearest Smaller Values Problem.

Xin He, Chun-Hsi Huang

J. Parallel Distributed Comput., 2001

A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs.

Xin He

J. Algorithms, 2001

Finding a hamiltonian paths in tournaments on clusters - a provably communication-efficient approach.

Chun-Hsi Huang, Xin He

Proceedings of the 2001 ACM Symposium on Applied Computing (SAC), 2001

2000

A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs.

Xin He, Ming-Yang Kao, Hsueh-I Lu

SIAM J. Comput., 2000

Hierarchical Topological Inference on Planar Disc Maps.

Zhi-Zhong Chen, Xin He

Proceedings of the Computing and Combinatorics, 6th Annual International Conference, 2000

1999

Fast <i>RNC</i> and <i>NC</i> Algorithms for Maximal Path Sets.

Ryuhei Uehara, Zhi-Zhong Chen, Xin He

Theor. Comput. Sci., 1999

Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings.

Xin He, Ming-Yang Kao, Hsueh-I Lu

SIAM J. Discret. Math., 1999

An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications.

Xin He, Zhi-Zhong Chen

SIAM J. Comput., 1999

On the Linear-Cost Subtree-Transfer Distance between Phylogenetic Trees.

Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp

Algorithmica, 1999

Nonplanar Topological Inference and Political-Map Graphs.

Zhi-Zhong Chen, Xin He, Ming-Yang Kao

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

On computing the nearest neighbor interchange distance.

Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Louxin Zhang

Proceedings of the Discrete Mathematical Problems with Medical Applications, 1999

1998

Scheduling Interval Ordered Tasks in Parallel.

Sivaprakasam Sunder, Xin He

J. Algorithms, 1998

Compact Encodings of Planar Graphs via Canonical Orderings and Multiple Parentheses.

Richie Chih-Nan Chuang, Ashim Garg, Xin He, Ming-Yang Kao, Hsueh-I Lu

Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1997

Regular Edge Labeling of 4-Connected Plane Graphs and Its Applications in Graph Drawing Problems.

Goos Kant, Xin He

Theor. Comput. Sci., 1997

On Parallel Selection and Searching in Partial Orders: Sorted Matrices.

R. Sarnath, Xin He

J. Parallel Distributed Comput., 1997

Grid Embedding of 4-Connected Plane Graphs.

Xin He

Discret. Comput. Geom., 1997

Parallel Algorithms for Maximal Acyclic Sets.

Zhi-Zhong Chen, Xin He

Algorithmica, 1997

On Floorplans of Planar Graphs.

Xin He

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Shortest Path in Complete Bipartite Digraph Problem and its Applications.

Xin He, Zhi-Zhong Chen

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

On Distances between Phylogenetic Trees (Extended Abstract).

Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Louxin Zhang

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

1996

Parallel Complexity of Partitioning a Planar Graph Into Vertex-induced Forests.

Zhi-Zhong Chen, Xin He

Discret. Appl. Math., 1996

An NC Algorithm for Finding a Minimum Weighted Completion Time Schedule on Series Parallel Graphs.

Sivaprakasam Sunder, Xin He

Algorithmica, 1996

Fast RNC and NC Algorithms for Finding a Maximal Set of Paths with an Application.

Ryuhei Uehara, Zhi-Zhong Chen, Xin He

Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

1995

on Determining Non-isotopic Configurations of Points on a Circle.

Xin He, David B. Sher

Discret. Appl. Math., 1995

An Efficient Parallel Algorithm for Finding Rectangular Duals of Plane Triangular Graphs.

Xin He

Algorithmica, 1995

NC Algorithms for Partitioning Planar Graphs into Induced Forests and Approximating NP-Hard Problems.

Zhi-Zhong Chen, Xin He

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1995

1994

Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs.

Ming-Yang Kao, Martin Fürer, Xin He, Balaji Raghavachari

SIAM J. Discret. Math., 1994

Regular Edge Labelings and Drawings of Planar Graphs.

Xin He, Ming-Yang Kao

Proceedings of the Graph Drawing, DIMACS International Workshop, 1994

1993

Two Algorithms for Finding Rectangular Duals of Planar Graphs.

Goos Kant, Xin He

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1993

Parallel Construction of Canonical Ordering and Convex Drawing of Triconnected Planar Graphs.

Xin He, Ming-Yang Kao

Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

1992

Parallel Algorithm for Cograph Recognition with Applications.

Xin He

Proceedings of the Algorithm Theory, 1992

O(n log log n)-Work Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs.

Martin Fürer, Xin He, Ming-Yang Kao, Balaji Raghavachari

Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992

1991

Efficient Parallel Algorithms for Series Parallel Graphs.

Xin He

J. Algorithms, 1991

An Improved Algorithm for the Planar 3-Cut Problem.

Xin He

J. Algorithms, 1991

An Efficient Parallel Algorithm for Finding Minimum Weight Matching for Points on a Convex Polygon.

Xin He

Inf. Process. Lett., 1991

1990

A P-Complete Graph Partition Problem.

R. Sarnath, Xin He

Theor. Comput. Sci., 1990

An Efficient Algorithm for Edge Coloring Planar Graphs with Delta Colors.

Xin He

Theor. Comput. Sci., 1990

Efficient Parallel Algorithms for r-Dominating Set and p-Center Problems on Trees.

Xin He, Yaacov Yesha

Algorithmica, 1990

Efficient Parallel and Sequential Algorithms for 4-Coloring Perfect Planar Graphs.

Xin He

Algorithmica, 1990

1988

A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs.

Xin He, Yaacov Yesha

SIAM J. Comput., 1988

Binary Tree Algebraic Computation and Parallel Algorithms for Simple Graphs.

Xin He, Yaacov Yesha

J. Algorithms, 1988

1987

Parallel Recognitions and Decomposition of Two Terminal Series Parallel Graphs

Xin He, Yaacov Yesha

Inf. Comput., October, 1987