Graph Theory and Algorithms
A graph is a collection of nodes and edges.
For example, a computer network consisting of computers at each node
and communication links as edges would form a graph. Other examples include,
layout of
streets and signals in a city, electrical circuits,
distances on a map and innumerable number of applications that involve
representation of relationship between objects. Natural questions
relating to graphs include, shortest route between nodes, connectivity
of the graph, reliability if links or nodes were removed, finding smaller
structures in larger graphs, specific cycles in graphs and drawing
of graphs onto surfaces.
Consider drawing a graph onto a plane without edges crossing. A complete graph on 4 vertices, can be redrawn but a complete graph on five vertices cannot. Now consider the same graph drawing on higher dimensional surfaces such as torus, etc. This research attempts to answer questions such as:
a) How many drawings of a graph (without
edge crossing) is possible on a given surface?
b) What is the complexity of algorithms
that draw graphs on various surfaces?
c) Can one find if graphs are isomorphic
by examining drawings on higher dimensional surfaces?
and several other questions relating to
graph drawing.
Publications
Journals
Conferences(Upcoming and Old)
ACMComputing
Surveys
ArsCombinatoria
Algorithmica
Combinatorica
DiscreteApplied
Mathematics
DiscreteMathematics
DiscreteMathematics
and Theoretical Computer Science
TheElectronic
Journal of Combinatorics and World Combinatorics Exchange
European
Journal of Combinatorics
Graphs
and Combinatorics
Information
and Computation
InformationProcessing
Letters
International Journal of Foundations of Computer Science
Journalof
the ACM
Journalof
Algorithms
Journalof
Complexity
Journalof
Computer and System Sciences
Journalof
Combinatorial Designs
Journalof
Combinatorial Optimization
Journalof
Combinatorial Theory, Series A
Journalof
Combinatorial Theory, Series B
Journalof
Graph Algorithms and Applications
Journalof
Graph Theory
LMSJournal
of Computation and Mathematics
Mathematical
Structures in Computer Science
NordicJournal
of Computing
SIAMJournal
on Computing
SIAMJournal
on Discrete Mathematics
SIAM
Journal on Scientific Computing
TheoreticalComputer
Science
1." Graph Ear Decompositions and Imbeddings ", To appear in SIAM Journal of Discrete Mathematics. (coauthor: J. Chen) , 1999.
2."A note on Approximating Graph Genus", In Information Processing Letters, 61, 1997, pp 317322 (coauthors: J. Chen and A. Kanevsky)
3."Tight lower bound on maximum genus of simplicial graphs" In Discrete Mathematics, 156, 1996, pp83102. (coauthors: J. Chen and J.L Gross)
4."Maximum Genus and Connectivity of a General Graph", Technical Report, Texas A & M University, Submitted to Journal of Graph Theory, 1996. (co-author: J. Chen)
5."Tight Lower bound on 2-connected simplicial graphs" , Technical Report, Texas A & M University, 1996, Submitted to Discrete Mathematics. (coauthor: J. Chen)
6."Determining Isomorphism of graphs", In GMI Industry Symposium, 1996
7."Number of vertices of a graph with maximum genus k" Manuscript, GMI Engineering & Management Institute, 1995, (coauthor: Frank Harary)
8."Polynomial time Algorithm for embeddings of graphs with bounded genus " Manuscript, GMI Engineering & Management Institute, 1994
9."Maximum genus and Trivalent graphs" , Manuscript, GMI Engineering and Management Institute, 1994
10."Graph Imbeddings and Graph Ear Decompositions", In Lecture Notes in Computer Science, 790, 1993, 376387, (coauthor: J. Chen)
11."On complexity of graph imbeddings", In Lecture Notes in Computer Science,709, 1993, pp 234245. (coauthors: J. Chen and A. Kanevsky)
12."On Graph Drawings with Smallest Number of Faces", in Graph Drawing, 1993, pp4043. (coauthors: J. Chen and J. L. Gross)
13."Hamiltonian Circuit in 2-regular digraphs",In
Open Problems, SIAM Journal of Discrete Mathematics Summer 1993.
Conference Home Pages
AGTIVE:
Applications of Graph Transformation with Industrial Relevance
AGTIVE99