Index: /trunk/src/org/openstreetmap/josm/data/APIDataSet.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/APIDataSet.java	(revision 6775)
+++ /trunk/src/org/openstreetmap/josm/data/APIDataSet.java	(revision 6776)
@@ -232,7 +232,14 @@
         relationsToAdd.removeAll(noProblemRelations);
 
-        RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd);
+        RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true);
         newToAdd.addAll(graph.computeUploadOrder());
         toAdd = newToAdd;
+
+        LinkedList<OsmPrimitive> newToDelete = new LinkedList<OsmPrimitive>();
+        newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class));
+        newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class));
+        graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false);
+        newToDelete.addAll(graph.computeUploadOrder());
+        toDelete = newToDelete;
     }
 
@@ -268,16 +275,12 @@
      */
     private static class RelationUploadDependencyGraph {
-        private Map<Relation, Set<Relation>> children;
+        private Map<Relation, Set<Relation>> children = new HashMap<Relation, Set<Relation>>();
         private Collection<Relation> relations;
-        private Set<Relation> visited;
+        private Set<Relation> visited = new HashSet<Relation>();
         private List<Relation> uploadOrder;
-
-        public RelationUploadDependencyGraph() {
-            this.children = new HashMap<Relation, Set<Relation>>();
-            this.visited = new HashSet<Relation>();
-        }
-
-        public RelationUploadDependencyGraph(Collection<Relation> relations) {
-            this();
+        private final boolean newOrUndeleted;
+
+        public RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) {
+            this.newOrUndeleted = newOrUndeleted;
             build(relations);
         }
@@ -286,10 +289,10 @@
             this.relations = new HashSet<Relation>();
             for(Relation relation: relations) {
-                if (!relation.isNewOrUndeleted() ) {
+                if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) {
                     continue;
                 }
                 this.relations.add(relation);
                 for (RelationMember m: relation.getMembers()) {
-                    if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
+                    if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) {
                         addDependency(relation, (Relation)m.getMember());
                     }
Index: /trunk/test/unit/org/openstreetmap/josm/data/osm/APIDataSetTest.java
===================================================================
--- /trunk/test/unit/org/openstreetmap/josm/data/osm/APIDataSetTest.java	(revision 6775)
+++ /trunk/test/unit/org/openstreetmap/josm/data/osm/APIDataSetTest.java	(revision 6776)
@@ -145,4 +145,48 @@
     }
 
+    @Test // for ticket #9624
+    public void deleteOneParentTwoNewChildren() {
+        DataSet ds = new DataSet();
+        Relation r1 = new Relation(1);
+        ds.addPrimitive(r1);
+        r1.put("name", "r1");
+
+        Relation r2 = new Relation(2);
+        ds.addPrimitive(r2);
+        r2.put("name", "r2");
+
+        Relation r3 = new Relation(3);
+        ds.addPrimitive(r3);
+        r3.put("name", "r3");
+
+        Relation r4 = new Relation(4);
+        ds.addPrimitive(r4);
+        r4.put("name", "unrelated");
+
+
+        r1.addMember(new RelationMember("", r2));
+        r1.addMember(new RelationMember("", r3));
+
+        r1.setDeleted(true);
+        r2.setDeleted(true);
+        r3.setDeleted(true);
+        r4.setDeleted(true);
+
+
+        APIDataSet apiDataSet = new APIDataSet();
+        apiDataSet.init(ds);
+        try {
+            apiDataSet.adjustRelationUploadOrder();
+        } catch(CyclicUploadDependencyException e) {
+            fail("unexpected exception:" + e);
+        }
+        List<OsmPrimitive> toDelete = apiDataSet.getPrimitivesToDelete();
+
+        assertEquals(4, toDelete.size());
+        assertEquals(true, toDelete.indexOf(r2) < toDelete.indexOf(r1));
+        assertEquals(true, toDelete.indexOf(r3) < toDelete.indexOf(r1));
+        assertEquals(true, toDelete.indexOf(r3) < toDelete.indexOf(r1));
+    }
+
     @Test
     public void oneCycle() {