• Speaker: Paul Samuel, Kuwait University
  • Title: Convex Partition and Graph Embedding
  • Location: Room V31, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Time and Date: 3:00 pm, Thu, 6th Aug 2015
  • Abstract:

    Partitioning is a basic fundamental technique in graph theory. Graph partitioning technique is used widely to solve several combinatorial problems. We will discuss the role of edge partitioning techniques on graph embedding. The graph embedding includes some combinatorial problems such as bandwidth problem, wirelength problem, forwarding index problem etc and in addition includes some cheminformatics problems such as Wiener Index, Szeged Index, PI index etc. In this seminar, we study convex partition and its characterization. In addition, we also analyze the relationship between convex partition and some other edge partitions such as Szeged edge partition and channel edge partition. The graphs that induce convex partitions are bipartite. We will discuss the difficulties in extending this technique to non-bipartite graphs.

  • [Permanent link]