Rao has two papers on sparsest cut in planar graphs, a constant-factor approximation in quasi-linear time seems possible. Recursive bisection, while not ideal, might be a feasible approach for your problem.
Satish Rao. Finding near optimal separators in planar graphs. In 28th Symposium on Foundations of Computer Science (FOCS), pages 225-237, 1987.
BAM, here's the answer. Incremental min cut graph partitions in $O(k^3)$ time for insertions and deletions. If you make $k = O(\log n)$ then it's poly logarithmic for insertions and deletions, which is damn good.
Dillencourt, Michael B.; Smith, Warren D. Graph-theoretical conditions for inscribability and Delaunay realizability. Discrete Math. 161 (1996), no. 1-3, 63–77.
However, if a topological triangulation has no separating triangles, and no chords connecting pairs of vertices on its outer face, then it is always realizable as a Delaunay triangulation....
Testing whether a pair of points $p_i$ and $p_j$ are the endpoints of a Delaunay edge can be solved as a linear programming feasability problem: Lift each point to one higher dimension by making its last coordinate be the sum of squares of the other coordinates. Then look for a hyperplane passing through $p_i$ and $p_j$, such that all the other points are on ...
(In 2-space,) a Delaunay triangulation is a planar graph. All planar graphs have average degree at most 6. So, many (all?) operations that depend on vertex degree of a Delaunay triangulation will run in $O(1)$ expected time.
Here's a theta bound on the expected value of the maximum degree of any vertex in a DT:
$\Theta (\log n / \log \log n)$
Here's the paper: http://www.ics.uci.edu/~eppstein/pubs/BerEppYao-IJCGA-91.pdf. If anyone else finds other properties, let me know!
This animation from the wikipedia article on delaunay triangulations shows you an example of where the delaunay triangulation will switch from having a horizontal interior edge to a vertical interior edge:
The moment this configuration switches to a ...
Alper Ungor did some nice work related to this issues of how do Delaunay refinement with alternative points. See his paper:
A. Ungor. Off-centers: A new type of Steiner points for computing size-optimal guaranteed-quality Delaunay triangulations. Computational
Geometry: Theory and Applications (CGTA), 42(2): 109--118, 2009.
Just insert sufficient number of points along the edges of the triangle you want - if you insert enough points, the edges of the triangle you want would be the union of edges of the triangulation. It is not pretty but it would work. This the basic idea behind many of the constrained triangulation meshing algorithms. Here is a nice paper on the topic, which ...
I think only those vertices corresponding to triangles sharing an edge with boundary or holes of the polygon will be of degree less than 3. Now the number of triangles in the triangulation is fixed. So you can always get the exact ratio of the number of degree 3 vertices for a polygon.
If the polygon has $k$ vertices and $l$ holes vertices and the number of ...
The following algorithm might help.
1. Choose any vertex from the graph.
2. Do a BFS untill $O(K)$ vertices has been visited.
3. Create a cluster with the visited vertices. (Connectivity is ensured for the cluster).
4. Remover the visited vertices from the graph.
5. Repeat 1-4 untill all nodes are visited.
Every cluster contains $O(K)$ vertices and ...