The main goals of the workshop are to facilitate the exchange of tools, techniques, questions, and ideas that will lead to a better understanding of geometric graphs that arise in different applications. Our objective is to gather researchers working on these topics in order to exchange the ideas for further research. The focus will be mainly on open problems and exploring possible approaches to solve them. We are also planning to arrange 3-4 plenary talks (45-60 min) from eminent researchers in these fields, and 5-6 shorter talks (25-30 min). The invited attendees of this workshop will also be requested to present open problems. The talks and presentation of open problems will be in the forenoon session. The afternoon session is left for discussion among researchers for solving those problems. During the workshop, we plan to focus on the following research areas:

Combinatorial questions on geometric graphs: The study of geometric graphs is a classical topic in computational geometry. Many practical problems have natural models via geometric objects. For example, map labeling, problems in wireless and sensor networks and VLSI physical design, database queries, etc. Here the vertices of the graph are mapped to some geometric objects and an edge between a pair of vertices indicates the existence of some specific relation depending on the problem. Here, the objectives are three fold, namely (i) characterizing the graph to have some desired embedding in IR^d, for some chosen d, depending on the problem specification, (ii) combinatorial questions regarding various properties of the graph, for example, minimum number of layers required to draw the graph in planar way, coloring vertices/edges with minimum number of colors to avoid conflict among the objects/paths, showing the relationship among different parameters of the graph, namely coloring number, clique size, etc., (iii) algorithmic questions regarding polynomial time computation of some parameters of the graph, or approximating the parameters to a desired accuracy in polynomial time, etc.

For an example, we may refer to the following problems on a geometric complete graph Gwith n points: (i) maximum number of planar spanning trees of G that can be packed in G, (ii) maximum number of plane perfect matching of the vertices in G that can be packed in G, (iii) maximum number of plane Hamiltonian paths in G that can be packed in G. All these questions are still unanswered.

Optimization problems on complete geometric bipartite graphs: Similarly, for a geometric bipartite graph G with bichromatic point set R∪B, where the set R (resp. B) are red (resp. blue) points, |R| = |B|, the following optimization problems require further research: (i) computing the minimum weight maximal planar matching, (ii) computing a perfect matching with minimum number of crossing, etc.

For a geometric graph with n points with edges colored by k colors (k < n－1), a minimum length spanning tree with at least one edge of each color may be an interesting problem to study. In addition, there are a lot of open questions related to the bounds of the spanning ratios on such geometric graphs.

Random Geometric Graphs: In recent years, a lot of progress has been made in the study of geometric intersection graphs, but many important combinatorial and algorithmic questions are still open. Recently, in the network science community the interest is growing towards the geometrical characterization of real network. A large real network is usually considered as a random graph (Erdos and Renyi (1960)). It is assumed that each pair of vertices in the network is connected with probability p, and is independent of the other edges of the graph. Here, the desired problems are modeled by random walk on geometric graphs for the average case analysis of the performance of the corresponding network. On the other hand, random geometric graph was first formally suggested by Gilbert (1961), whose vertices are random points in Euclidean plane and an edge between a pair of points (nodes) exists if their distance is less than a given constant r. These classes of graphs are known to have numerous applications as a model for studying communication primitives (broadcasting, routing, etc.) and topology control (connectivity, coverage, etc.) in idealized wireless sensor networks as well as extensive utility in theoretical computer science and many fields of the mathematical sciences, namely routing problems in the internet, data mining, community detection, to name a few.

Many important problems are still unsolved for random geometric graphs. For example, given a geometric k-NN (k nearest neighbor) graph G with n random points in IR2 and each point is connected with its k nearest neighbors for a given value of k, the lower and upper bounds on k for the graph G to be connected are 0.3043 log n and 0.5139 log n respectively [Balister, Bollobas, Sarkar and Walters 2006]. It will be interesting to tighten the bound on k for the connectivity of G. Also for a directed complete graph G with the edge cost of each directed edge ( pi,pj ) is α if pj is the α-th nearest neighbor of pi, computing (i) the expected cost of minimum spanning tree, (ii) expected value of the spanning ratio between the farthest pair of points, etc. will be interesting problems to study.